Public key cryptosystems are globally deployed on the World Wide Web, as well as on a growing number of enterprise networks, for establishment of secure communication channels. Every user in a public key cryptosystem has a pair of keys including a public key and a private key. The public key is disclosed to other users while the private key is kept secret. A public key cryptosystem typically has a primary designed use, such as for encryption, digital signature, or key agreement. Public key cryptosystems are also used for user authentication. For example, a user can authenticate itself to other users by demonstrating knowledge of its private key, which other users can verify using the corresponding public key.
In an application of a public key cryptosystem for authenticating a user, the public key must be securely associated with the identity of the user that owns the public key by authenticating the public key itself. Public key certificates are typically employed to authenticate the public key. A public key certificate is a digital document, signed by a certificate authority, that binds a public key with one or more attributes that uniquely identify the owner of the public key. The public key certificate can be verified using the certificate authority's public key, which is assumed to be well known or is recursively certified by a higher authority. For example, in a corporation, a public key certificate can bind a public key to an employee number.
A public key infrastructure (PKI) refers to the collection of entities, data structures, and procedures used to authenticate public keys. A traditional PKI comprises a certificate authority, public key certificates, and procedures for managing and using the public key certificates.
One type of a user of a PKI owns the public key contained in a public key certificate and uses the certificate to demonstrate the user's identity. This type of user is referred to as the subject of the certificate or more generally as the subject. Another type of user relies on a public key certificate presented by another user to verify that the other user is the subject of the certificate and that the attributes contained in the certificate apply to the other user. This type of user that relies on the certificate is referred to as a verifier or relying party.
The association between a public key and an identity can become invalid because the attributes that define the identity no longer apply to the owner of the public key, or because the private key that corresponds to the public key has been compromised. A PKI typically employs two complementary techniques for dissociating a public key from an identity. In the first technique, each public key certificate has a validity period defined by an expiration date, which is a substantial period from the issue date, such as one year from the issue date. In the second technique, the certificate authority revokes a public key certificate if the public key certificate's binding becomes invalid before the expiration date. One way of revoking a public key certificate is by including a serial number of the public key certificate in a certificate revocation list (CRL), which is signed and issued by the certificate authority at known periodic intervals, such as every few hours or once a day. An entity that relies on a certificate is responsible for obtaining the latest version of the CRL and verifying that the serial number of the public key certificate is not on the list.
CRLs typically become quite long very quickly. When the CRLs become long, performance is severely impacted. First, CRL retrieval consumes large amounts of network bandwidth. Second, each application has to retrieve the CRL periodically, parse the CRL, and allocate storage for the CRL. Then, the application needs to carry out a linear search of the CRL for the public key certificate serial number when the application verifies each public key certificate. As a result, conventional PKIs do not scale beyond a few thousand users.
One solution proposed to alleviate the linear search problem is to partition CRLs. The serial number of the public key certificate determines where the CRL partition is located when the public key certificate is revoked. With partitioned CRLs, the application still has to retrieve and store the entire CRL or else the application needs to fetch a CRL partition in order to verify a certificate. Since certificate verification is a likely critical path, fetching a CRL partition impacts the time it takes to run the application.
An on-line certificate status protocol (OCSP) operates by permitting the verifier of the public key certificate to ask the certificate authority if the certificate is currently valid. The certificate authority responds with a signed statement. The OCSP allows CRLs to be avoided, but requires the verifier to query the certificate authority as part of the transaction that employs the public key certificates. The verifier querying the certificate authority increases the time it takes to perform the transaction. The OCSP scheme is highly vulnerable to a denial-of-service attack, where the attacker floods the certificate authority with queries. Responding to each query is computationally expensive, because each response requires a digital signature.
In a certificate status proofs scheme, the certificate authority maintains a data structure describing the set of valid and invalid certificates in the directory. For every public key certificate that has not yet expired, a short cryptographic proof can be extracted from the data structure of the certificate's current status (i.e., valid or invalid). A CRL can essentially be viewed as a cryptographic proof of invalidity for the public key certificates in the CRL, and proof of validity for those not in the CRL. The CRL, however, is not a short proof. The short cryptographic proof can be obtained by the verifier from the directory, or it can be obtained by the subject and presented to the verifier together with the public key certificate.
The Simple Public Key Infrastructure (SPKI) working group of the Internet Society and the Internet Engineering Task Force has proposed the possibility of employing short-lived certificates as a method of achieving fine-grain control over the validity interval of a certificate. See C. M. Ellison, B. Frantz, B. Lampson, R. Rivest, B. M. Thomas and T. Ylonen, SPKI Certificate Theory, Request for Comments 2560 of the Internet Engineering Task Force, September 1999. The SPKI certificate theory reference states that there are cases in which a short-lived certificate requires fewer signatures and less network traffic than various on-line test options. The use of a short-lived certificate always requires fewer signature verifications than the use of a certificate plus on-line test result.
Nevertheless, no practical method of issuing short-lived certificates has been proposed. Traditional certificates are issued off-line, as part of a process that includes subject registration, at the rate of one per year per user. By contrast, short-lived certificates would have to be issued on-line at the rate of at least one per day per user, and perhaps as often as one every few minutes for every user.
The term on-line and the term off-line have particular definitions in the context of a PKI. The term on-line herein refers to the day-to-day usage of public key certificates and key pairs for authentication. The term off-line herein refers to the more infrequent establishment or dissolution of public key bindings, which may result in the issuing or revocation of public key certificates. For example, the traditional certificate authority is off-line, issues CRLs off-line, and places the CRLs in a directory for on-line retrieval. The scheme involving certificate status proofs also makes use of off-line certificate authorities. The OCSP is the only scheme described above that employs an on-line certificate authority.
In a traditional PKI, a public key is authenticated by a certificate signed by a certificate authority. If the private key associated with the public key is compromised, the subject of the certificate notifies the certificate authority, which revokes the certificate.
It is conceivable, however, that the same private/public key pair could be used for multiple purposes. For some purposes, the public key traditionally could be authenticated by one or more traditional certificates, issued by one or more certificate authorities. For other purposes, the public key may be known directly to one or more verifiers, and thus may not have to be authenticated.
If a private/public key pair is used for multiple purposes, when the private key is compromised it becomes necessary to prevent further use of the key pair for any of the multiple purposes. Revoking a single certificate is no longer sufficient to prevent all uses of the private/public key pair. Thus, it would be desirable to provide a practical way for a single action taken by the owner of the private/public key pair to prevent any further use of the key pair that would allow an impostor to masquerade as the legitimate owner of the key pair.
Ecommerce Scenario
It would be desirable in an ecommerce scenario to have multiple uses of a single public/private key pair. In current ecommerce applications, the retailer's web server demonstrates its identity using a public/private key pair and a public key certificate signed by a certificate authority whose public key is configured into the browsers. The customer, on the other hand, demonstrates the customer's identity by a password, sent encrypted after a Secure Sockets Layer (SSL) connection has been established between the browser and the server. The password is established when the customer registers with the retailer's ecommerce site, and is used to identify the customer on repeat visits to the site.
Although passwords are sent encrypted, this use of passwords is vulnerable because customers are likely to use the same password to access all sites. An insider attack at one web site may provide the attacker with passwords that can be used to masquerade for users at other sites, such as at popular sites where most ecommerce customers have an account. An attacker could also set up a fake ecommerce site with the only purpose of collecting passwords from customers in order to access those customers' accounts at other sites.
Because of this vulnerability of passwords, there is a need for the use of public key cryptography for client authentication, in addition to its current use for web server authentication. The SSL protocol allows the web browser to submit a client certificate to the server and to demonstrate knowledge of the private key associated with the public key contained in the certificate. The private key may be stored in a smart card for protection against software attack.
The traditional PKI paradigm for ecommerce calls for the client certificate to be signed by a certificate authority independent of any particular ecommerce retailer, such as by a commercial certificate authority (e.g., Verisign). However, it is unlikely that an ecommerce site will accept a certificate issued by a third party certificate authority, because the ecommerce site would have to trust the certificate authority to establish the identity of the customer. Ecommerce retailers have developed their own processes for registering customers, tailored to their specific needs. Thus, ecommerce retailers are unlikely to abandon their own processes and rely instead on registration by one or more third party certificate authorities over which they have no control.
Therefore, there is a desire for an alternative PKI paradigm for ecommerce in which the customer could register the customer's public key directly with the ecommerce site, as part of the customer registration process. It is desirable that in such an alternative PKI paradigm that the customer could provide the customer's public key, instead of a password, when registering with the site. To avoid modifying SSL, it would be desirable to have the customer send the public key in a self-signed client certificate.
In such ecommerce scenario, each customer has a private/public key pair, with the private key safely stored and used in a smart card, and registers the public key with many different ecommerce sites. Thus, the private/public key pair is used for many purposes. When the private key is compromised, the customer must prevent use of the private/public key pair at all ecommerce sites where the customer has registered the public key, and just remembering these sites could be a difficult task for the customer. Thus, there is a need for a new mechanism which allows the customer to prevent further use of the private/public key pair at all sites by taking a single action.
Ron Rivest, R. L. Rivest, Can we Eliminate Certificate Revocation Lists?, Proceedings of Financial Cryptography, 1998, (“the Rivest Reference”) has proposed a way of preventing use of a private/public key pair after the private key has been compromised. The method proposed in the Rivest Reference makes use of an association of suicide bureaus. The owner of a private/public key pair registers the public key with a suicide bureau. When the private/public key is compromised, the owner signs a suicide note using the private key and sends the suicide note to the suicide bureau, which broadcasts the suicide note to the association. While the private key is not compromised, the owner can obtain a certificate of health for the public key and present it to a verifier together with a public key certificate. The certificate of health is a digital document signed by the suicide bureau asserting that the suicide bureau has registered the public key and is not aware of any suicide note for that public key.
One drawback of the suicide bureau method proposed in the Rivest Reference is that after the legitimate owner of a private/public key pair has registered the public key with a first suicide bureau, an attacker can register the same public key with a different suicide bureau, in anticipation of gaining knowledge of the private key. If the attacker later does gain knowledge of the private key, and the compromise is detected, the legitimate owner of the private/public key pair will send a suicide note to the first suicide bureau, but the attacker may still obtain a certificate of health from the second suicide bureau. To prevent this, all suicide bureaus must belong to a single association and must be linked by a reliable broadcast network, which will be difficult to achieve in practice. The second suicide bureau must listen on the network and invalidate its record of the private key, even though the suicide note is for a public key that had been registered with the first suicide bureau.
A second drawback of the proposed suicide bureau method is that after a public key has been compromised and the suicide note has been broadcast to all suicide bureaus, an attacker could register the public key in a new registration with the same or with a different suicide bureau, and could then obtain certificates of health based on the new registration. To prevent this, every suicide bureau must maintain a perfect record of every public key registered in any suicide bureau for which a suicide note has ever been issued. This, again, is difficult to achieve in practice.
A third method drawback of the proposed suicide bureau method is that the method is only applicable to private/public key pairs that belong to a signature cryptosystem, because the private key must be used to sign the suicide note. In particular, the method cannot be used for key pairs belonging to the Diffie-Hellman (DH) cryptosystem, since a Diffie-Hellman private key cannot be used to sign documents.
Thus, there is a need for an improved way of preventing use of a private/public key pair after the private key has been comprised which does not have the above drawbacks of the suicide bureau method proposed in the Rivest Reference.